#include <iostream>

struct TreeNode
{
    TreeNode(const int & element):data(element)
    {
        left = right = nullptr;
    }
    int data;  //数据域
    TreeNode *left;  //左孩子指针
    TreeNode *right;  //右孩子指针
};

TreeNode *root = nullptr;  //根节点指针

const int SIZE = 100;
TreeNode *nodes[SIZE] = {nullptr};


void SelectTwoMinNodes(int size,int &min1,int &min2)
{
    min1 = min2 = -1;
    for(int i = 0;i < size;i++)
    {
        if(nodes[i] != nullptr)
        {
            if(min1 == -1 || nodes[i]->data < nodes[min1]->data)
            {
                min2 = min1;
                min1 = i;
            }
            else if(min2 == -1 || nodes[i]->data < nodes[min2]->data)
            {
                min2 = i;
            }
        }
    }
}

void BuildHuffmanTree(int *a,int size)
{
    
    for(int i = 0;i < size;i++)
    {
        nodes[i] = new TreeNode(a[i]);  //把数组结点都变成树结点
    }

    for(int i = 0;i < size - 1;i++)
    {
        int min1,min2;  //最小的两个结点
        SelectTwoMinNodes(size,min1,min2);
        TreeNode *newNode = new TreeNode(nodes[min1]->data + nodes[min2]->data);
        newNode->left = nodes[min1];
        newNode->right = nodes[min2];

        nodes[min1] = newNode;
        nodes[min2] = nullptr;
    }

    for(int i = 0;i < size;i++)
    {
        if(nodes[i] != nullptr)
        {
            root = nodes[i];
            break;
        }
    }
}

void PrevTravel(TreeNode *node)
{
    if(node == nullptr)
    {
        return;
    }
    std::cout<<node->data<<" ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

void MidTravel(TreeNode *node)
{
    if(node == nullptr)
    {
        return;
    }
    MidTravel(node->left);
    std::cout<<node->data<<" ";
    MidTravel(node->right);
}

int main()
{
    int a[] = {5,9,12,13,16,45};
    BuildHuffmanTree(a,6);
    PrevTravel(root);
    std::cout<<std::endl;
    MidTravel(root);
    std::cout<<std::endl;
    return 0;
}